package uk.org.landeg.euler.problems;

import java.util.HashSet;
import java.util.Set;

import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;
import uk.org.landeg.euler.problems.lib.Fraction;

public class Problem073 extends AbstractProblem {
	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem073());
		launcher.solve();
	}

	@Override
	public String getDescription() {
		// TODO Auto-generated method stub
		return "How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d 12,000?";
	}

	@Override
	public Integer getProblemNumber() {
		// TODO Auto-generated method stub
		return 73;
	}

	@Override
	public Object solve() {
		int count = 0;
		Set<Fraction> matches = new HashSet<Fraction>();
		Fraction f;
		double r, half = 1.0/2.0, third = 1.0/3.0, val;
		int dmax;
		for (int n = 2 ; n <= 12000 ; n++) {
			dmax = n/2+1;
			for (int d = 1 ; d <= dmax ; d++) {
				val = (double)d/(double)n;
				if (val > third && val < half ) {
					matches.add(Fraction.reduce(new Fraction(d, n)));
				} else if (val > half) {
					break;
				}
			}
		}
		notes.add("Original runtime : 35439ms");
		
		return matches.size();
	}

}
